package done.easy_201_300;

import com.study.common.TreeNode;
import lombok.extern.slf4j.Slf4j;
import org.junit.Test;

import static com.study.util.LogUtil.info;
import static com.study.util.SwapUtil.swap;

/**
 * 226. Invert Binary Tree
 * 翻转一棵二叉树。
 * <p>
 * 示例：
 * 输入：
 * <p>
 * 4
 * /   \
 * 2     7
 * / \   / \
 * 1   3 6   9
 * <p>
 * 输出：
 * <p>
 * 4
 * /   \
 * 7     2
 * / \   / \
 * 9   6 3   1
 *
 * @author wangxiaozhe
 */
@Slf4j
public class InvertBinaryTree {

    @SuppressWarnings("all")
    public TreeNode invertTree(TreeNode root) {
        // 190325 first
        // 190401 second
        // 190517 third
        // 190604 fourth 非递归，看了答案一遍过
        return root;
    }

    @Test
    public void test() {
        TreeNode root = new TreeNode(4,
                new TreeNode(2,
                        1, 3), new TreeNode(7,
                6, 9));
        info("before:{}", root);
        TreeNode newroot = invertTree(root);
        info("after:{}", newroot);
    }
}








































/*
// 方法一（性能最好）非递归实现翻转
public TreeNode invertTree(TreeNode root) {
    LinkedList<TreeNode> stack = new LinkedList<>();
    stack.push(root);

    while (!stack.isEmpty()) {
        TreeNode tempRoot = stack.pop();
        swap(tempRoot.left, tempRoot.right);

        if (tempRoot.left != null) {
            stack.push(tempRoot.left);
        }

        if (tempRoot.right != null) {
            stack.push(tempRoot.right);
        }
    }
    return root;
}

// 方法二
public TreeNode invertTree(TreeNode root) {
    if (root == null) {
        return null;
    }

    // 1.  父节点立刻旋转
    TreeNode tmp = root.left;
    root.left = root.right;
    root.right = tmp;

    // 2.  子节点的递归旋转
    // 2.1 递归旋转左边的
    invertTree(root.left);

    // 2.2 递归旋转右边的
    invertTree(root.right);

    return root;
}

// 方法三
public TreeNode invertTree(TreeNode root) {
    if (root==null)
        return null;

    TreeNode left = invertTree(root.left);

    TreeNode right = invertTree(root.right);

    root.left = right;
    root.right = left;

    return root;
}
*/
